home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / set.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.6 KB  |  62 lines
  1. {\magonebf 3.8 Sets  (set)}
  2.  
  3. \decl set E 
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $S$ of the parameterized data type \name\ is a collection of 
  8. elements of the linearly ordered type $E$, called the element type of $S$. The 
  9. size of $S$ is the number of elements in $S$, a set of size zero is called the 
  10. empty set.
  11.  
  12.  
  13. \bigskip
  14. {\bf 2. Creation}
  15.  
  16.  
  17. \create S {} 
  18.  
  19. creates an instance \var\ of type \name\ and initializes it to the empty set.
  20.  
  21. \bigskip
  22. {\bf 3. Operations}
  23.  
  24. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  25. \+\op void insert  {E\ x} 
  26.                          {adds $x$ to \var}
  27. \smallskip
  28. \+\op void del     {E\ x} 
  29.                          {deletes $x$ from \var}
  30. \smallskip
  31. \+\op bool member  {E\ x} 
  32.                          {returns true if $x$ in \var, false otherwise}
  33. \smallskip
  34. \+\op E    choose  {}    
  35.                          {returns an element of \var.}
  36. \+\nop                   {\precond \var\ is not empty.}
  37. \smallskip
  38. \+\op bool empty   {}    
  39.                          {returns true if \var\ is empty, false otherwise}
  40. \smallskip
  41. \+\op int  size    {}    
  42.                          {returns the size of \var}
  43. \smallskip
  44. \+\op void clear   {}    
  45.                          {makes \var\ the empty set}
  46.  
  47.  
  48. \bigskip
  49. {\bf 4. Iteration}
  50.  
  51.  
  52. {\bf forall}($x,S$) 
  53. $\{$  ``the elements of $S$ are successively assigned to $x$''  $\}$
  54.  
  55. \bigskip
  56. {\bf 5. Implementation}
  57.  
  58. Sets are implemented by randomized search trees ([AS89]). Operations insert,
  59. del, member take time $O(\log n)$, empty, size take time $O(1)$, and clear 
  60. takes time $O(n)$, where $n$ is the current size of the set.
  61.  
  62.